Error-correcting codes are widely used in many fields of information technology, particularly in the transfer of information between a transmitter and a receiver, and the storing/reading of information on a storage medium.
LDPC codes are error-correcting codes in the linear block code category whose parity-check matrix is sparse (“low-density parity check matrix”), meaning that it contains a small number of non-zero elements in comparison to the total number of elements. As they are linear block codes, they can be characterized by a parity-check matrix, usually denoted H. The parity-check matrix H is linked to a matrix called a code generator matrix, generally denoted G, by the relation G·HT=0, where HT denotes the transposed matrix of H. The dimensions M×N of the parity-check matrix correspond, for the number of rows M, to the number of parity-check constraints of the code, and for the number of columns N, to the length of the codewords of the code considered. As the rows of the parity-check matrix Hof a linear block code respectively correspond to parity-check constraints which are constructed to be satisfied by the codewords, the equality ν·HT=0 will be satisfied for any codeword ν.
As a reminder, a Galois field GF(q) is a finite set of q elements in which any element can be described as a function of a primitive element, here denoted α. Below, the elements of the Galois field GF(q) will be denoted {0, α0, α1, . . . , αq−2}.
LDPC codes in which the symbols of the codewords belong to the binary Galois field (order 2), denoted GF(2), are known as binary LDPC codes, while LDPC codes in which the symbols of the codewords belong to a Galois field of order q strictly greater than 2, denoted GF(q), are known as non-binary. Thus, the elements of a parity-check matrix of a non-binary LDPC code belong to a non-binary (q>2) Galois field GF(q) and the matrix products of the above equations will be obtained using the laws of addition and multiplication for the field GF(q), respectively denoted ⊕ and  in the following description.
The construction of these codes can also be determined by a set of parity-check equations over GF(q), where one of these equations involving dc codeword symbols is written: Σk=1dchj,kxk=0 where hj,k are the non-zero values in the jth row of H, and a codeword is denoted by X=(x1, x2, . . . , xN) where (xk), k=1 . . . N is a symbol represented by m=log2(q) bits denoted xk(xk,1xk,2 . . . xk,m).
An example of a parity-check matrix H in Galois field GF(4) in which the elements are denoted {0; α0; α1; α2}, of dimensions M=3 and N=6, is given below:
  H  =      (                            0                                      α            0                                                              α              0                        ⁢            0                                                α            2                                    0                                                  α            1                                    0                                      0            ⁢                                                  ⁢                          α              0                                                0                                      α            2                                                            α            0                                    0                                                    α              2                        ⁢            0                                    0                                      α            1                                )  
Many iterative algorithms for decoding LDPC codes use a bipartite graph representation of the parity-check matrix for the code, called a “Tanner graph.” For a parity-check matrix H of dimensions M×N, this representation uses edges to connect M nodes, called “parity-check nodes” or “check nodes” (CN), with N nodes, called “variable nodes” (VN). Each non-zero element of the parity-check matrix is represented in the corresponding Tanner graph by an edge connecting the parity-check node corresponding to the row of the element in the matrix H to the variable node corresponding to the column of the element in the matrix H. Each parity-check node of the graph thus represents a parity-check equation determined by the edges that connect it to the variable nodes. The variable nodes receive the words to be decoded or that are being decoded.
FIG. 1 shows the Tanner graph corresponding to the above example of a parity-check matrix of dimensions M=3 and N=6. This graph contains M=3 parity-check nodes labeled CN1, CN2 and CN3 in the figure, and N=6 variable nodes labeled VN1, VN2, VN3, VN4, VN5 and VN6 in the figure. The three parity-check equations respectively corresponding to the three parity-check nodes of the graph are:α0VN2⊕α0VN3⊕α2VN5=0 for parity-check node CN1,α1VN1⊕α0VN4⊕α2VN6=0 for parity-check node CN2,α0VN1⊕α2VN3⊕α1VN6=0 for parity-check node CN3,
where the operators ⊕ and  respectively indicate addition and multiplication in the Galois field GF(4).
The Tanner graphical representation can be used to implement algorithms of demonstrated efficiency in graphical models, such as the “belief propagation” (BP) algorithm, or “Message passing” (MP) algorithms. When applied to a bipartite graph with two different types of nodes, the BP algorithm is based on an iterative process of sending messages between nodes of each type connected by edges (the nodes are said to be “neighbors”).
Iterative algorithms for LDPC decoding using the exchange of messages between the parity-check nodes and variable nodes of the Tanner graph corresponding to the LPDC code in question have thus been developed. These decoding algorithms can be more generally used or adapted for decoding all linear block codes having a representation as a bipartite graph comprising a set of parity-check nodes and a set of variable nodes.
In the case of soft-input decoding, the exchanged messages contain possible values of the symbols of the codewords processed, with associated likelihood or reliability information. For example, when the code concerned is binary, and the symbols of the codewords have values in the Galois field GF(2) or in other words are binary values, the exchanged messages containing probability densities include two densities, one for the value “0” and the other for the value “1”. The messages include, for example, pairs of binary values which are respectively associated with likelihood values (or reliability values).
When the code concerned is non-binary, and the symbols of the codewords are values in the Galois field GF(q) with q>2, the messages exchanged may contain q reliability values, each corresponding to an element of GF(q), which can be represented as a vector of size q of (symbol, reliability value) pairs.
A parity-check node of a non-binary LDPC decoder for a code with values in the Galois field GF(q) thus receives dc input messages and generates dc, output messages. Each input and output message contains q pairs of values, one representing a symbol and the other representing a reliability or likelihood associated with this symbol. If using a direct implementation of the Belief Propagation (BP) decoding algorithm, output is constructed by selecting the q best combinations among q to the power dc−1. This leads to a computational complexity on the order of O(q2). The BP decoding algorithm can also be considered in the frequency domain. It is then called a Fourier Transform-based BP algorithm. Changing to the frequency domain can reduce the complexity of the BP algorithm to achieve a complexity on the order of O(dc×q×log(q)). However, the cost of implementing the BP algorithm still remains very high in terms of computational complexity, and becomes prohibitive when considering values of q exceeding 16.
Various algorithms have been proposed to solve this high complexity issue, including the Extended Min-Sum (EMS) algorithm, which proposes using truncated messages by selecting the most reliable nm symbols, nm being chosen to be well below q (nm«q). The messages are then sorted before being introduced to the parity-check node. A parity-check node is composed of a combination of elementary parity-check nodes, where each elementary parity-check node receives two sorted messages each containing nm (symbol, reliability) pairs from which it generates an output message containing the nm best possible combinations of two input messages, the total number of combinations being equal to nm to the power of 2.
One can refer to the following article for a detailed description of the EMS algorithm: “Decoding algorithms for nonbinary LDPC codes over GF(q)”, D. Declercq and M. Fossorier, IEEE Trans. Commun., vol. 55, no. 4, pp. 633-643, April 2007.
The “Bubble Check” algorithm and its improved version known as “L-Bubble Check”, which aim to further reduce the complexity of the elementary parity-check nodes while maintaining the same performance in terms of error rates, propose reducing the search space of the nm best possible combinations of the two input messages.
One can refer to the following articles for a detailed description of the Bubble Check and L-Bubble Check algorithms, respectively: “Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders”, E. Boutillon and L. Conde-Canencia, Electronics Letters, vol. 46, no. 9, pp. 633-634, 2010; and “Design of a GF(64)-LDPC Decoder Based on the EMS Algorithm”, Boutillon E., L. Conde-Canencia, A. Al Ghouwayel, IEEE Trans. On Circuits and Systems, vol. 60, no. 10, pp. 2644-2656, October 2013.
Although the Bubble-Check algorithm allows reducing the number of calculations in the elementary parity-check nodes, the decoding complexity is still too high to allow truly efficient hardware and/or software implementations.